package leetcode.code1201;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int nthUglyNumber(int n, int a, int b, int c) {
		long ans = 0;
		long l = 0, r = (long) Math.min(a, Math.min(b, c)) * n;
		long ab = this.lcm(a, b);
		long ac = this.lcm(a, c);
		long bc = this.lcm(b, c);
		long abc = this.lcm(b, ac);
		while (l <= r) {
			long m = l + ((r - l) >> 1);
			long N = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;
			if (N < n) {
				l = m + 1;
				ans = l;
			} else {
				r = m - 1;
			}
		}
		return (int) ans;
	}

	private long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	private long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
